#include "../BinTree/BinTree.hpp"
#ifndef _BST_HPP_
#define _BST_HPP_

template <class T> class BST: public BinTree<T> {
public:
	virtual BinNodePosi(T) &search(const T &e);
	virtual BinNodePosi(T) insert(const T &e);
	virtual bool remove(const T &e);
protected:
	/**
	 * @brief The parent of the "hit" node
	 * 
	 */
	BinNodePosi(T) _hot;
	/**
	 * @brief Connect 3 nodes and 4 subtrees according to the "3 + 4" principle 
	 * 
	 */
	BinNodePosi(T) connect34(
		BinNodePosi(T), BinNodePosi(T), BinNodePosi(T),
		BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T));
	/**
	 * @brief rotate p and its parent and ancestor
	 * 
	 */
	BinNodePosi(T) rotateAt(BinNodePosi(T) p);

};

#include "BST_implemention.hpp"

#endif